/*
 * @lc app=leetcode.cn id=91 lang=java
 *
 * [91] 解码方法
 */

// @lc code=start
class Solution {
    public int numDecodings(String s) {
        if(s.charAt(0)=='0') return 0;
        int len = s.length();
        int[] dp = new int[len+1];//dp[i]表示前i个字符解码的方法数
        dp[0]=1;
        for(int i = 1 ;i<=len ;i++){
            if(s.charAt(i-1)=='0'&&(s.charAt(i-2)>'2'||s.charAt(i-2)=='0')) return 0;//证明至少是30，不可能转成字母
            if(s.charAt(i-1)!='0'){//取第i个字符，这个数不为0，可以继承之前的方法数。
                dp[i] += dp[i-1];
            }
            if(i>1 && (s.charAt(i-2)=='2'||s.charAt(i-2)=='1')&&s.charAt(i-1)<='6'){//取i-1和i-2两个字符，若其位于[1,26]范围内，则可以加dp[i-2]
                dp[i] +=dp[i-2];
            }
        }
        return dp[len];
    }
}
// @lc code=end

